package uk.ac.glasgow.demosocs.impl.util;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.SortedMap;
import java.util.TreeMap;
/**
 * Utility implementation code.  This class may be modified, adapted and/or integrated the DemoSOCS system as desired.
 * @author tws
 *
 */
public class Util {

	public static void main(String[] args){
		Collection<RankedVote> votes = new ArrayList<RankedVote>();
		votes.add(new RankedVote("A","B","C"));
		votes.add(new RankedVote("A","B","C"));
		votes.add(new RankedVote("C","A","B"));
		votes.add(new RankedVote("C","A","B"));
		votes.add(new RankedVote("A","B","C"));
		votes.add(new RankedVote("A","B","C"));

		System.out.println(computeAVResult(votes,0));		
	}

	
	/**
	 * A utility method for calculating the result of an election held under the alternative vote system.  
	 * @param votes a list of lists of GUID candidate identifiers.
	 * @param seed a seed for a random generator for deciding ties.
	 * @return an ordering of unique 
	 */
	public static List<String> computeAVResult(Collection<RankedVote> votes, Integer seed){
		
		//Initialise the random number generator
		Random r = new Random(seed);
		
		//The array for holding the candidates in order of elimination (reverse order). 
		List<String> eliminated = new ArrayList<String>();
		
		if (votes.size() < 1) return null;
				
		//The piles of votes to allocate each vote to, depending on the current preference.
		Map<String,Collection<RankedVote>> piles = new HashMap<String,Collection<RankedVote>>();
		
		//Do the initial allocation of votes to piles.
		for (RankedVote vote: votes){
			String topPreference = vote.getTopPreference();
			
			Collection<RankedVote> pile = piles.get(topPreference);
			if (pile == null){
				pile = new ArrayList<RankedVote>();
				piles.put(topPreference, pile);
			}
			pile.add(vote);
		}
		
				
		//Now progressively eliminate piles of votes, based on pile size.
		while (piles.size() > 0){
			System.out.println(piles);
			
			//Group the piles by size so that the smallest pile(s) can be found.
			TreeMap<Integer,List<Collection<RankedVote>>> pilesBySize =
				new TreeMap<Integer,List<Collection<RankedVote>>>();
			
			for (Collection<RankedVote> pile: piles.values()){
				List<Collection<RankedVote>> pileBySize = pilesBySize.get(pile.size());
				if (pileBySize == null){
					pileBySize = new ArrayList<Collection<RankedVote>>();
					pilesBySize.put(pile.size(), pileBySize);
				}
				pileBySize.add(pile); 
			}
			
			//Get the list of smallest piles.
			List<Collection<RankedVote>> smallestPiles = pilesBySize.firstEntry().getValue();
			
			//Choose one of the smallest piles at random from the list to be eliminated.
			Integer index = r.nextInt(smallestPiles.size());
			Collection<RankedVote> smallestPile = smallestPiles.get(index);
			
			String leastPreferred = smallestPile.iterator().next().getTopPreference();
			
			// Now distribute the votes from the smallest pile to the other candidates.
			piles.remove(leastPreferred);
			
			for (RankedVote vote: smallestPile){
												
				//initialise the search variables
				RankedVote nextPreferences = vote;
				Collection<RankedVote> receivingPile = null;
				
				//then work down the preferences until a valid pile is discoverered
				while (receivingPile == null && nextPreferences != null){
					nextPreferences = nextPreferences.getTailPreferences();
					if (nextPreferences != null){
						String nextPreference = nextPreferences.getTopPreference();
						receivingPile = piles.get(nextPreference);
					}
				}
				if (receivingPile != null) receivingPile.add(nextPreferences);				
			}
			
			//Add the eliminated candidate to the list
			eliminated.add(leastPreferred);
		}
		
		//Finally, reverse and return the list of eliminated candidates.
		Collections.reverse(eliminated);
		return eliminated;
	}	
}

class RankedVote  {
	
	private TreeMap<Integer,String> preferences;
	
	public RankedVote(String... preferences){
		this.preferences = new TreeMap<Integer,String>();
		
		for (int i = 0; i < preferences.length; i++)
			this.preferences.put(i, preferences[i]);
	}
	
	private RankedVote(TreeMap<Integer,String> preferences){
		this.preferences = preferences;
	}
		
	public String getTopPreference(){
		if (size() > 0)
			return preferences.firstEntry().getValue();
		else return null;
	}
	
	public int size (){
		return preferences.size();
	}
	
	public RankedVote getTailPreferences(){
		if (size() > 1){
			Integer highestPreference = preferences.firstKey();
			Integer nextPreference = preferences.higherKey(highestPreference);
		
			SortedMap<Integer,String> lower = preferences.tailMap(nextPreference);
		
			return new RankedVote(new TreeMap<Integer,String>(lower));
		} else return null;
	}
	
	public String toString(){
		return preferences.toString();
	}
}
